class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));

        for (int i = 0; i < n; ++i)
        {
            dp[0][i] = 0;
            dp[1][i + 1] = matrix[0][i];
        }

        int MinNum = INT_MAX;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = min({ dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1] })
                    + matrix[i - 1][j - 1];

                if (i == m && dp[i][j] < MinNum)
                    MinNum = dp[i][j];
            }
        }

        return MinNum;
    }
};